{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Darts Inside of a Circular Dartboard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numPoints"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #圆形靶内的最大飞镖数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>Alice 向一面非常大的墙上掷出 <code>n</code> 支飞镖。给你一个数组 <code>darts</code> ，其中 <code>darts[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> 表示 Alice 掷出的第 <code>i</code> 支飞镖落在墙上的位置。</p>\n",
    "\n",
    "<p>Bob 知道墙上所有 <code>n</code> 支飞镖的位置。他想要往墙上放置一个半径为 <code>r</code> 的圆形靶。使 Alice 掷出的飞镖尽可能多地落在靶上。</p>\n",
    "\n",
    "<p>给你整数 <code>r</code> ，请返回能够落在 <strong>任意</strong> 半径为 <code>r</code> 的圆形靶内或靶上的最大飞镖数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1 ：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/04/29/sample_1_1806.png\" style=\"width: 248px; height: 211px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>darts = [[-2,0],[2,0],[0,2],[0,-2]], r = 2\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>如果圆形靶的圆心为 (0,0) ，半径为 2 ，所有的飞镖都落在靶上，此时落在靶上的飞镖数最大，值为 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2 ：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/04/29/sample_2_1806.png\" style=\"width: 306px; height: 244px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>darts = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>如果圆形靶的圆心为 (0,4) ，半径为 5 ，则除了 (7,8) 之外的飞镖都落在靶上，此时落在靶上的飞镖数最大，值为 5 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= darts.length &lt;= 100</code></li>\n",
    "\t<li><code>darts[i].length == 2</code></li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>darts</code> 中的元素互不相同</li>\n",
    "\t<li><code>1 &lt;= r &lt;= 5000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-darts-inside-of-a-circular-dartboard](https://leetcode.cn/problems/maximum-number-of-darts-inside-of-a-circular-dartboard/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-darts-inside-of-a-circular-dartboard](https://leetcode.cn/problems/maximum-number-of-darts-inside-of-a-circular-dartboard/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[-2,0],[2,0],[0,2],[0,-2]]\\n2', '[[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]]\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numPoints(self, points: List[List[int]], r: int) -> int:\n",
    "        n = len(points)\n",
    "\n",
    "        def getinsidecount(cx, cy):\n",
    "            res = 0\n",
    "            for p in points:\n",
    "                x, y = p\n",
    "                if (x - cx)**2 + (y - cy)**2 <= r**2:\n",
    "                    res += 1\n",
    "            return res\n",
    "\n",
    "        res = 1\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                x1, y1 = points[i]\n",
    "                x2, y2 = points[j]\n",
    "                d2 = (x1 - x2)**2 + (y1 - y2)**2\n",
    "                if d2 > (2 * r)**2:\n",
    "                    continue\n",
    "                px, py = (x1 + x2) / 2, (y1 + y2) / 2\n",
    "                dx, dy = x1 - x2, y1 - y2\n",
    "                h = math.sqrt(r**2 - d2 / 4)\n",
    "                for fx, fy in ((1, -1), (-1, 1)):\n",
    "                    # 解有两个, 符号正好相反\n",
    "                    cx = fx * h * dy / math.sqrt(dx**2 + dy**2) + px\n",
    "                    cy = fy * h * dx / math.sqrt(dx**2 + dy**2) + py\n",
    "                    res = max(res, getinsidecount(cx, cy))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPoints(self, darts: List[List[int]], r: int) -> int:\n",
    "        def center(x1, y1, x2, y2):\n",
    "            d = ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5\n",
    "            if d > 2 * r: return []\n",
    "            a = (x1 + x2) / 2\n",
    "            b = (y1 + y2) / 2\n",
    "            c = (r ** 2 - (d / 2) ** 2) ** 0.5\n",
    "            return [[a + c * (y1 - y2) / d, b - c * (x1 - x2) / d],\n",
    "                    [a - c * (y1 - y2) / d, b + c * (x1 - x2) / d]]\n",
    "\n",
    "        def count(x, y):\n",
    "            return sum((x - x1) ** 2 + (y - y1) ** 2 <= r ** 2 + 1e-8 for x1, y1 in darts)\n",
    "\n",
    "        ans = 1\n",
    "        for i in range(len(darts)):\n",
    "            for j in range(i + 1, len(darts)):\n",
    "                for x, y in center(darts[i][0], darts[i][1], darts[j][0], darts[j][1]):\n",
    "                    ans = max(ans, count(x, y))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "darts = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]]\n",
    "r = 5\n",
    "\n",
    "def judge(x, y, r):\n",
    "    return ((x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2) <= r ** 2 + 1e-5\n",
    "\n",
    "\n",
    "def find(a, b, x, y, r):\n",
    "    mid = ((a + x) / 2., (b + y) / 2.)\n",
    "\n",
    "    l1 = ((a - x) ** 2 + (b - y) ** 2) ** 0.5 / 2.\n",
    "    if l1 > r:\n",
    "        return ((0, 0), (0, 0))\n",
    "    l2 = (r ** 2 - l1 ** 2) ** 0.5\n",
    "\n",
    "    fx, fy = (x - a) / 2., (y - b) / 2.\n",
    "    sx, sy = l2 * fx / l1, l2 * fy / l1\n",
    "\n",
    "    return ((mid[0] - sy, mid[1] + sx), (mid[0] + sy, mid[1] - sx))\n",
    "\n",
    "class Solution:\n",
    "    def numPoints(self, darts: List[List[int]], r: int) -> int:\n",
    "        \n",
    "        n = len(darts)\n",
    "        ans = 1\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if i != j:\n",
    "                    p1, p2 = find(*darts[i], *darts[j], r)\n",
    "\n",
    "                    tot = 0\n",
    "                    for k in darts:\n",
    "                        if judge(k, p1, r):\n",
    "                            tot += 1\n",
    "                    \n",
    "                    if ans < tot: ans = tot\n",
    "\n",
    "                    tot = 0\n",
    "                    for k in darts:\n",
    "                        if judge(k, p2, r):\n",
    "                            tot += 1\n",
    "                    \n",
    "                    if ans < tot: ans = tot\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def numPoints(self, points: List[List[int]], r: int) -> int:\n",
    "        def check(x, y):\n",
    "            ans = 0\n",
    "            for i, j in points:\n",
    "                if (i-x)**2 + (j-y)**2 <= r**2 + 0.001:\n",
    "                    ans += 1\n",
    "            return ans \n",
    "        def f(x, y):\n",
    "            x1, y1 = x\n",
    "            x2, y2 = y\n",
    "            if (x1 - x2)**2 + (y1 - y2)**2 > (2*r)**2:\n",
    "                return 1 \n",
    "            elif (x1 - x2)**2 + (y1 - y2)**2 == (2*r)**2:\n",
    "                x = (x1+x2)/2 \n",
    "                y = (y1+y2)/2 \n",
    "                z = [(x, y)]\n",
    "                ans = 0\n",
    "                for x, y in z:\n",
    "                    ans = max(ans, check(x, y))\n",
    "                return ans \n",
    "\n",
    "            else:\n",
    "                x3 = (x1+x2)/2 \n",
    "                y3 = (y1+y2)/2 \n",
    "                d = math.sqrt(r**2 - (math.sqrt((x1-x2)**2 + (y1-y2)**2)/2)**2)\n",
    "                if y1==y2:\n",
    "                    z = [(0, 1), (0, -1)]\n",
    "                else:\n",
    "                    k = -(x2 - x1)/(y2 - y1)\n",
    "                    x1 = math.sqrt(1/(1 + (x2-x1)**2/(y2-y1)**2)  )\n",
    "                    x2 = -x1 \n",
    "                    \n",
    "                    y1 = k*x1 \n",
    "                    y2 = k*x2\n",
    "                    z = [(x1, y1), (x2, y2)]\n",
    "                z = [(x*d + x3, y*d + y3) for x, y in z]  \n",
    "                ans = 0\n",
    "                for x, y in z:\n",
    "                    ans = max(ans, check(x, y))\n",
    "                return ans \n",
    "        ans = 0\n",
    "        n = len(points)\n",
    "        if n==1:\n",
    "            return 0 \n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                print( f(points[i], points[j]), points[i], points[i])\n",
    "                ans = max(ans, f(points[i], points[j]))\n",
    "        return ans \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPoints(self, points: List[List[int]], r: int) -> int:\n",
    "        def helper(i, r, n):\n",
    "            angles = []\n",
    "            for j in range(n):\n",
    "                if i != j and (l2 := sum([_ ** 2 for _ in vec[i][j]])) <= (2 * r) ** 2 + 1e-8:\n",
    "                    C = math.acos(math.sqrt(l2) / (2 * r))\n",
    "                    T = math.atan2(vec[i][j][1], vec[i][j][0])\n",
    "                    _in = T - C\n",
    "                    _out = T + C\n",
    "                    angles.append([_in, True])\n",
    "                    angles.append([_out, False])\n",
    "            # 这里排序是重点, 考虑边界条件\n",
    "            # 比如有 [0, False], [0, True]\n",
    "            # 要让[0, True] 排到 [0, False]前面\n",
    "            angles.sort(key=lambda x: [x[0], - x[1]])\n",
    "            cnt = res = 1\n",
    "            for item in angles:\n",
    "                if item[1]:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    cnt -= 1\n",
    "                if cnt > res:\n",
    "                    res = cnt\n",
    "            return res\n",
    "\n",
    "        n = len(points)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        # vec[i][j] = [Jx - Ix, J_y - Iy]\n",
    "        # vec 存入两点之间的方向向量\n",
    "        vec = [[[0, 0] for _ in range(n)] for __ in range(n)]\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                JxIx = points[j][0] - points[i][0]\n",
    "                JyIy = points[j][1] - points[i][1]\n",
    "                vec[i][j] = [JxIx, JyIy]\n",
    "                vec[j][i] = [-JxIx, -JyIy]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, helper(i, r, n))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numPoints(self, points: List[List[int]], r: int) -> int:\n",
    "        \n",
    "        def helper(i, r, n):\n",
    "            angles = []\n",
    "            for j in range(n):\n",
    "                if i != j and (l2 := sum([_ ** 2 for _ in vec[i][j]])) <= (2 * r) ** 2 + 1e-8:\n",
    "                    C = math.acos(math.sqrt(l2) / (2 * r))\n",
    "                    T = math.atan2(vec[i][j][1], vec[i][j][0])\n",
    "                    _in = T - C\n",
    "                    _out = T + C\n",
    "                    angles.append([_in, True])\n",
    "                    angles.append([_out, False])\n",
    "            angles.sort(key=lambda x: [x[0], - x[1]])\n",
    "            cnt = res = 1\n",
    "            for item in angles:\n",
    "                if item[1]:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    cnt -= 1\n",
    "                if cnt > res:\n",
    "                    res = cnt\n",
    "            return res\n",
    "        n = len(points)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        vec = [[[0]*2]*(n+1) for __ in range(n)]\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                JxIx = points[j][0] - points[i][0]\n",
    "                JyIy = points[j][1] - points[i][1]\n",
    "                vec[i][j] = [JxIx, JyIy]\n",
    "                vec[j][i] = [-JxIx, -JyIy]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, helper(i, r, n))\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numPoints(self, points: List[List[int]], r: int) -> int:\n",
    "        \n",
    "        def helper(i, r, n):\n",
    "            angles = []\n",
    "            for j in range(n):\n",
    "                if i != j and (l2 := sum([_ ** 2 for _ in vec[i][j]])) <= (2 * r) ** 2 + 1e-8:\n",
    "                    C = math.acos(math.sqrt(l2) / (2 * r))\n",
    "                    T = math.atan2(vec[i][j][1], vec[i][j][0])\n",
    "                    _in = T - C\n",
    "                    _out = T + C\n",
    "                    angles.append([_in, True])\n",
    "                    angles.append([_out, False])\n",
    "            # 这里排序是重点, 考虑边界条件\n",
    "            # 比如有 [0, False], [0, True]\n",
    "            # 要让[0, True] 排到 [0, False]前面\n",
    "            angles.sort(key=lambda x: [x[0], - x[1]])\n",
    "            cnt = res = 1\n",
    "            for item in angles:\n",
    "                if item[1]:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    cnt -= 1\n",
    "                if cnt > res:\n",
    "                    res = cnt\n",
    "            return res\n",
    "\n",
    "        n = len(points)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        vec = [[[0, 0] for _ in range(n)] for __ in range(n)]\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                JxIx = points[j][0] - points[i][0]\n",
    "                JyIy = points[j][1] - points[i][1]\n",
    "                vec[i][j] = [JxIx, JyIy]\n",
    "                vec[j][i] = [-JxIx, -JyIy]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, helper(i, r, n))\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPoints(self, points: List[List[int]], r: int) -> int:\n",
    "        def helper(i, r, n):\n",
    "            angles = []\n",
    "            for j in range(n):\n",
    "                if i != j and (l2 := sum([_ ** 2 for _ in vec[i][j]])) <= (2 * r) ** 2 + 1e-8:\n",
    "                    C = math.acos(math.sqrt(l2) / (2 * r))\n",
    "                    T = math.atan2(vec[i][j][1], vec[i][j][0])\n",
    "                    _in = T - C\n",
    "                    _out = T + C\n",
    "                    angles.append([_in, True])\n",
    "                    angles.append([_out, False])\n",
    "            # 这里排序是重点, 考虑边界条件\n",
    "            # 比如有 [0, False], [0, True]\n",
    "            # 要让[0, True] 排到 [0, False]前面\n",
    "            angles.sort(key=lambda x: [x[0], - x[1]])\n",
    "            cnt = res = 1\n",
    "            for item in angles:\n",
    "                if item[1]:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    cnt -= 1\n",
    "                if cnt > res:\n",
    "                    res = cnt\n",
    "            return res\n",
    "\n",
    "        n = len(points)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        # vec[i][j] = [Jx - Ix, J_y - Iy]\n",
    "        # vec 存入两点之间的方向向量\n",
    "        vec = [[[0, 0] for _ in range(n)] for __ in range(n)]\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                JxIx = points[j][0] - points[i][0]\n",
    "                JyIy = points[j][1] - points[i][1]\n",
    "                vec[i][j] = [JxIx, JyIy]\n",
    "                vec[j][i] = [-JxIx, -JyIy]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, helper(i, r, n))\n",
    "\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
